package com.wtgroup.demo.leetcode.q017_电话号码的字母组合;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**回溯
 * @author dafei
 * @version 0.1
 * @date 2021/4/6 12:04
 */
public class Q017_M3_回溯 {

    public static void main(String[] args) {
        String[] inputs = {/*"23", */""/*, "2"*/};
        Q017_M3_回溯 exe = new Q017_M3_回溯();
        for (String input : inputs) {
            System.out.println(exe.letterCombinations(input));
        }
    }

    static Map<Character, String> phoneMap;
    static {
        phoneMap =new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};
    }

    public List<String> letterCombinations(String digits) {

        //#1 一个有效解容器
        List<String> container = new ArrayList<>();
        if (digits == null || digits.length()==0) {
            return container;
        }
        //#2 一个路径内容容器
        StringBuffer buff = new StringBuffer();
        backtrack(digits, container, 0, buff);
        return container;
    }

    public static void backtrack(String digits, List<String> container, int index, StringBuffer buff) {
        //#3 路径走到头, 收集有效解
        if (index == digits.length()) {
            container.add(buff.toString());
        } else {
            char[] alphas = phoneMap.get(digits.charAt(index)).toCharArray();
            //#4 平行节点挨个往下递归
            for (char c : alphas) {
                buff.append(c);
                backtrack(digits, container, index+1, buff);
                //#5 递归结束, 自然回溯
                // 回溯回来了, 后面的内容砍掉
                buff.delete(index, buff.length());
            }
        }
    }

}
